#pragma once

#include <string>
#include <vector>

#include "NumberExcep.hpp"

namespace header
{

class Number
{
public:
    friend std::istream& operator>>(std::istream& is, Number& number);
    friend std::ostream& operator<<(std::ostream& os, const Number& number);

public:
    using size_type = std::string::size_type;

public:
    static const int PRECISION = 6;

public:
    enum class DivFlag  /* 小数最后一个保留方式 */
    {
        round,          // 四舍五入
        truncate        // 截断
    };

public:
    Number() :_digit{ "0" }, _point{ 0 }, _signed{ false}, _width{ 1 } { }
    // @param flag false: 删除后导零 true: 保留后导零
    Number(const char*        num, bool flag = false) :Number(std::string{num}, flag) { }
    // @param flag false: 删除后导零 true: 保留后导零
    Number(const std::string& num, bool flag = false) 
        :_digit{ num }, _width{ static_cast<int>(num.size()) } 
    { 
        if (!is_legal_number(_digit)) throw NumberExcep{"illegal number: " + num};
        cal_digit_point_signed(_digit, _point, _signed, flag);
    }
    ~Number() = default;
    
public:
    Number  operator+ (const Number& other)
    {
        if (!_signed) {
            if (!other._signed) return Number{add_double(_digit, _point, other._digit, other._point)};
            else return Number{sub_double(_digit, _point, other._digit, other._point)};
        }
        else {
            if (!other._signed) return Number{sub_double(other._digit, other._point, _digit, _point)};
            else return Number{"-" + add_double(_digit, _point, other._digit, other._point)};
        }
        return Number{};
    }

    Number& operator+=(const Number& other)
    {
        *this = (*this) + other;
        return *this;
    }

    Number  operator- (const Number& other)
    {
        if (!_signed) {
            if (!other._signed) return Number{sub_double(_digit, _point, other._digit, other._point)};
            else return Number{add_double(_digit, _point, other._digit, other._point)};
        }
        else {
            if (!other._signed) return Number{"-" + add_double(_digit, _point, other._digit, other._point)};
            else return Number{sub_double(other._digit, other._point, _digit, _point)};
        }
        return Number{};
    }
    
    Number& operator-=(const Number& other)
    {
        *this = (*this) - other;
        return *this;
    }
    
    Number  operator* (const Number& other)
    {
        if (!_signed) {
            if (!other._signed) return Number{mul_double(_digit, _point, other._digit, other._point)};
            else return Number{"-" + mul_double(_digit, _point, other._digit, other._point)};
        }
        else {
            if (!other._signed) return Number{"-" + mul_double(_digit, _point, other._digit, other._point)};
            else return Number{mul_double(_digit, _point, other._digit, other._point)};
        }
        return Number{};
    }
    
    Number& operator*=(const Number& other)
    {
        *this = (*this) * other;
        return *this;
    }

    // @brief 整除
    Number  operator/ (const Number& other)
    {
        if (!_signed) {
            if (!other._signed) return Number{div_double(_digit, _point, other._digit, other._point, 0, DivFlag::truncate)};
            else return Number{"-" + div_double(_digit, _point, other._digit, other._point, 0, DivFlag::truncate)};
        }
        else {
            if (!other._signed) return Number{"-" + div_double(_digit, _point, other._digit, other._point, 0, DivFlag::truncate)};
            else return Number{div_double(_digit, _point, other._digit, other._point, 0, DivFlag::truncate)};
        }
        return Number{};
    }
    // @brief 整除
    Number& operator/=(const Number& other)
    {
        *this = (*this) / other;
        return *this;
    }

    Number  operator% (const Number& other)
    {
        if (_signed) return Number{"-" + mod(_digit, _point, other._digit, other._point)};
        else return Number{mod(_digit, _point, other._digit, other._point)};
    }
    
    Number& operator%=(const Number& other)
    {
        *this = (*this) % other;
        return *this;
    }

    Number  operator^ (Number other)
    {
        bool is_signed = other._signed;
        other = Number{to_double(other._digit, other._point)};     // 避免 _digit = 20, _point = 1 => 2.0
        if (other._point != 0) throw NumberExcep{"Decimal exponents are not supported"};
        if (other == "0") return "1";
        if (*this == Number{ "0" }) return "0";
        Number res = "1";
        while (cmp_int(other._digit, "0") == 1) {
            if (other % "2" == "1") res *= (*this);
            other /= "2";
            *this *= (*this);
        }
        return (is_signed) ? Number{"1"}.div(res) : res;
    }

    Number& operator^=(const Number& other)
    {
        *this = (*this) ^ other;
        return *this;
    }
    
    Number& operator= (const Number& number)
    {
        _digit = number._digit;
        _point = number._point;
        _signed = number._signed;
        return *this;
    }
    
    bool    operator==(Number other)
    {
        // 避免后导零的影响
        Number cur{to_double(_digit, _point)};
        other = Number{to_double(other._digit, other._point)};
        return cur._digit == other._digit && cur._point == other._point && cur._signed == other._signed;
    }

    bool    operator!=(Number other)
    {
        return !(*this == other);
    }
    
    bool    operator> (const Number& other)  
    {
        if (_signed != other._signed) return _signed < other._signed;       // 1. 一正一负
        if (_signed == true) return cmp_double(_digit, _point, other._digit, other._point) != 1;    // 2. 两负
        return cmp_double(_digit, _point, other._digit, other._point) == 1;     // 3. 两正
    }
    
    bool    operator>=(const Number& other)
    {
        return *this > other || *this == other;
    }

    bool    operator< (const Number& other)
    {
        if (_signed != other._signed) return _signed > other._signed;       // 1. 一正一负
        if (_signed == true) return cmp_double(_digit, _point, other._digit, other._point) != -1;    // 2. 两负
        return cmp_double(_digit, _point, other._digit, other._point) == -1;     // 3. 两正
    }

    bool    operator<=(const Number& other)
    {
        return *this < other || *this == other;
    }

public:
    /**
     * @brief 小数除法
     * @param other 除数
     * @param n 保留小数位数
     * @param flag 小数最后一个保留的方式
     */
    Number      div(const Number& other, int n = PRECISION, DivFlag flag = DivFlag::round)
    {
        if (!_signed) {
            if (!other._signed) return Number{div_double(_digit, _point, other._digit, other._point, n, flag), true};
            else return Number{"-" + div_double(_digit, _point, other._digit, other._point, n, flag), true};
        }
        else {
            if (!other._signed) return Number{"-" + div_double(_digit, _point, other._digit, other._point, n, flag), true};
            else return Number{div_double(_digit, _point, other._digit, other._point, n, flag), true};
        }
        return Number{};
    }

    std::string str() const
    { 
        return (_signed) ? "-" + to_double(_digit, _point) : to_double(_digit, _point); 
    }
    // @brief 返回数字原本的长度
    size_type   width() const { return _width; }

#ifdef NUMBER_TEST_ON
public:  /* 方便做测试 */
#else
private:
#endif
    // @brief 判断是否是合法数字 (digits ['.' digits])
    bool is_legal_number(const std::string& num) const
    {
        if (num.empty() || num == ".") return false;
        int i = 0;
        if (num[0] == '-' || num[0] == '+') {
            i = 1;
        }
        bool is_float = false;
        auto len = num.size();
        for (; i < len; ++i) {
            if (num[i] == '.') {
                if (is_float) return false;
                is_float = true;
            }
            else if (!isdigit(num[i])) return false;
        }
        return true;
    }

    /**
     * @brief 根据小数(num >= 0)，计算数据部分 (直接删除小数点) 以及 小数位数
     */
    void cal_digit_point(std::string& num, int& point) const
    {
        auto pos = num.find('.');
        auto len = num.size();
        if (pos == std::string::npos) point = 0;
        else {
            num.erase(pos, 1);
            point = num.size() - pos;
        }
        delete_pre_0(num);
    }

    /**
     * @brief 根据 num 计算处 num 的数据部分、小数位数、是否有符号
     * @param num 根据输出的 num，输出只删除小数点后剩余的数据部分 num
     * @param point 小数位数
     * @param is_signed true: 负数
     * @param flag   false: 删除后导零 true: 保留后导零
     */
    void cal_digit_point_signed(std::string& num, int& point, bool& is_signed, bool flag = false) const
    {
        delete_pre_0(num);
        auto pos = num.find('.');
        //  .1 ==>  0.1
        // -.2 ==> -0.2
        if (pos == 0) num = "0" + num;
        else if (pos == 1 && !isdigit(num[0])) num.insert(num.begin() + 1, '0');
        if (flag == false) delete_suf_0(num);
        is_signed = (num[0] == '-');
        if (num == "-0") is_signed = false;
        if (num[0] == '+' || num[0] == '-') num.erase(0, 1);
        cal_digit_point(num, point);
    }

    // @brief 删除前导零，保留 0 (+0 -0 -> 0)
    void delete_pre_0(std::string& num) const
    {
        if (num.empty()) return;
        int pos = (num[0] == '+' || num[0] == '-') ? 1 : 0;
        int fir = pos;
        int len = num.size();
        for (; pos < len - 1; ++pos) {
            if (num[pos] != '0' || num[pos + 1] == '.') break;
        } 
        num.erase(fir, pos - fir);
        if (num == "+0" || num == "-0") num = "0";
    }

    // @brief 删除后导零 (3.0 -> 3)
    void delete_suf_0(std::string& num) const
    {
        auto pos = num.rfind('.');
        if (pos == std::string::npos) return;
        int i = num.size() - 1;
        for (; i > pos; --i) {
            if (num[i] != '0') break;
        }
        num = num.substr(0, i + 1);
        if (num.back() == '.') num.pop_back();
        if (num == "+0" || num == "-0") num = "0";
    }

    /**
     * @brief 已知小数的数据部分 (直接删除小数点) 以及 小数位数，返回带小数点的数据
     */
    std::string to_double(std::string num, int point) const
    {   
        if (num == "0") return "0";
        std::string begin = "";
        if (num[0] == '-' || num[0] == '+') {
            begin = num[0];
            num.erase(0, 1);
        }
        int len = num.size();
        int pos = len - point;
        if (pos == num.size()) {
            num = begin + num;
            return num;
        }
        if (pos < 0) {
            while (pos != 1) {
                num = "0" + num;
                ++pos;
            }
        }
        num.insert(num.begin() + pos, '.');
        if (num[0] == '.') num = "0" + num;
        num = begin + num;
        return num;
    }

    /**
     * @brief 正整数大小比较
     * @return 
     *      1) num1 > num2: 1
     *      2) num1 = num2: 0
     *      3) num1 < num2: -1
     */
    int cmp_int(std::string num1, std::string num2) const
    {
        if ((num1.size() > num2.size()) || (num1.size() == num2.size() && num1 > num2)) return 1; 
        else if ((num1.size() < num2.size()) || (num1.size() == num2.size() && num1 < num2)) return -1; 
        else return 0;
    }

    /**
     * @brief 正小数大小比较
     * @param num1 第一个浮点数的数据部分 (即直接删除小数点)
     * @param p1   第一个浮点数的小数点位数
     * @param num2 第二个浮点数的数据部分 (即直接删除小数点)
     * @param p2   第二个浮点数的小数点位数
     * @return 
     *      1) num1 > num2: 1
     *      2) num1 = num2: 0
     *      3) num1 < num2: -1
     */
    int cmp_double(std::string num1, int p1, std::string num2, int p2) const
    {
        int p = std::max(p1, p2);
        int dif = abs(p1 - p2);
        if (dif != 0) {
            if (p1 > p2) num2 = (num2 == "0") ? num2 : num2 + std::string(dif, '0');
            else num1 = (num1 == "0") ? num1 : num1 + std::string(dif, '0');
        }
        return cmp_int(num1, num2);
    }

    std::string add_int(std::string num1, std::string num2) const
    {
        std::string res;
        int cur = 0;
        int p1 = num1.size() - 1, p2 = num2.size() - 1;
        while (p1 >= 0 || p2 >= 0 || cur > 0) {
            if(p1 >= 0) cur += num1[p1--] - '0';
            if(p2 >= 0) cur += num2[p2--] - '0';
            res = std::to_string(cur % 10) + res;
            cur = cur / 10;
        }
        return res;
    }
    
    /**
     * @brief 浮点数加法
     * @param num1 第一个浮点数的数据部分 (即直接删除小数点)
     * @param p1   第一个浮点数的小数点位数
     * @param num2 第二个浮点数的数据部分 (即直接删除小数点)
     * @param p2   第二个浮点数的小数点位数
     * @return 返回正常的小数 (包含小数点)
     */
    std::string add_double(std::string num1, int p1, std::string num2, int p2) const
    {
        int p = std::max(p1, p2);
        int dif = abs(p1 - p2);
        if (dif != 0) {
            if (p1 > p2) num2 = (num2 == "0") ? num2 : num2 + std::string(dif, '0');
            else num1 = (num1 == "0") ? num1 : num1 + std::string(dif, '0');
        }
        std::string res = add_int(num1, num2);
        res = to_double(res, p);
        return res;
    }

    /**
     * @brief 正整数相减
     */
    std::string sub_int(std::string num1, std::string num2) const
    {
        bool is_signed = false;
        if (cmp_int(num1, num2) == -1) {
            std::swap(num1, num2);
            is_signed = true;
        }
        std::string res;
        int cur = 0;
        bool is_carry = false;      // 是否借位
        int len1 = num1.size() - 1, len2 = num2.size() - 1;
        while (len1 >= 0 || len2 >= 0 || cur > 0) {
            if(len1 >= 0) {
                cur += num1[len1--] - '0' - is_carry;
                is_carry = false;
            }
            if(len2 >= 0) cur -= num2[len2--] - '0';
            if (cur < 0) {
                cur += 10;
                is_carry = true;
            }
            res = std::to_string(cur) + res;
            cur = 0;
        }
        delete_pre_0(res);
        if (is_signed) res = "-" + res;
        return res;    
    }

    /**
     * @brief 浮点数减法
     * @param num1 第一个浮点数的数据部分 (即直接删除小数点)
     * @param p1   第一个浮点数的小数点位数
     * @param num2 第二个浮点数的数据部分 (即直接删除小数点)
     * @param p2   第二个浮点数的小数点位数
     * @return 返回正常的小数 (包含小数点)
     */
    std::string sub_double(std::string num1, int p1, std::string num2, int p2) const
    {
        int p = std::max(p1, p2);
        int dif = abs(p1 - p2);
        if (dif != 0) {
            if (p1 > p2) num2 = (num2 == "0") ? num2 : num2 + std::string(dif, '0');
            else num1 = (num1 == "0") ? num1 : num1 + std::string(dif, '0');
        }
        std::string res = sub_int(num1, num2);
        res = to_double(res, p);
        return res;
    }

    // @brief 将字符串长度扩展到 2 的幂
    void extend_str(std::string& s, size_t& len) const
    {
        while (len & (len - 1)) {
            ++len;
        }
        while (s.size() < len)
            s = '0' + s;
    }

    // @brief 较小的数使用 long long 乘法
    std::string naive_mul(std::string num1, std::string num2) const
    {
        long long x = std::atoi(num1.c_str());
        long long y = std::atoi(num2.c_str());
        return std::to_string(x * y);
    }

    std::string karatsuba_mul(std::string num1, std::string num2) const
    {
        if (num1 == "0" || num2 == "0") return "0";
    
        auto len = std::max(num1.size(), num2.size());
        extend_str(num1, len);
        extend_str(num2, len);
        if (num1.size() <= 8){
            return naive_mul(num1, num2);
        }
        auto index = len / 2;
        std::string x1(num1.begin(), num1.begin() + index);
        std::string x0(num1.begin() + index, num1.end());
        std::string y1(num2.begin(), num2.begin() + index);
        std::string y0(num2.begin() + index, num2.end());
        std::string p1 = karatsuba_mul(x1, y1);
        std::string p2 = karatsuba_mul(x0, y0);
        std::string x01 = add_int(x0, x1);
        std::string y01 = add_int(y0, y1);
        std::string p3 = karatsuba_mul(x01, y01);
        p3 = sub_int(p3, p1);
        p3 = sub_int(p3, p2);
        for (auto i = len; i > 0; i--)
            p1 += '0';
        for (auto i = index; i > 0; i--)
            p3 += '0';
        std::string res = add_int(p1, p2);
        res = add_int(res, p3);
        return res;
    }

    // // @brief 模拟手算乘法
    // std::string normal_mul(std::string num1, std::string num2) const
    // {
    //     int m = num1.size(), n = num2.size();
    //     std::vector<int> res(m + n);
    //     for (int i = m - 1; i >= 0; i--) {
    //         for (int j = n - 1; j >= 0; j--) {
    //             int mul = (num1[i] - '0') * (num2[j] - '0');
    //             int p1 = i + j, p2 = i + j + 1;
    //             int sum = mul + res[p2];
    //             res[p2] = sum % 10;
    //             res[p1] += sum / 10;
    //         }
    //     }
    //     int i = 0;
    //     while (i < res.size() && res[i] == 0) i++;
    //     std::string str;
    //     for (; i < res.size(); i++) str.push_back(res[i] + '0');
    //     return str.empty() ? "0" : str;
    // }

    std::string mul_int(std::string num1, std::string num2) const
    {
        return karatsuba_mul(num1, num2);
    }

    /**
     * @brief 浮点数乘法
     * @param num1 第一个浮点数的数据部分 (即直接删除小数点)
     * @param p1   第一个浮点数的小数点位数
     * @param num2 第二个浮点数的数据部分 (即直接删除小数点)
     * @param p2   第二个浮点数的小数点位数
     * @return 返回正常的小数 (包含小数点)
     */
    std::string mul_double(std::string num1, int p1, std::string num2, int p2) const
    {
        std::string res = mul_int(num1, num2);
        res = to_double(res, p1 + p2);
        return res;
    }

    /**
     * @brief 返回余数的除法 
     * @param num1 被除数，接收相除后的余数
     * @return 商
     */
    std::string divide(std::string& num1, std::string num2) const
    {
        if (num2 == "0") throw NumberExcep{"The divisor cannot be 0"};
        std::string res = "0";
        while (cmp_int(num1, num2) != -1) {
            num1 = sub_int(num1, num2);
            res = add_int(res, "1");
        } 
        return res;
    }   
    /**
     * @brief 计算 num1 / num2，保留 n 位小数 (如果能整除，无论 n 为几，都不保留小数)
     */
    std::string div_int(std::string num1, std::string num2, int precision = PRECISION, DivFlag flag = DivFlag::round) const
    {
        if (num2 == "0") throw NumberExcep{"The divisor cannot be 0"};
        if (num1 == "0") return "0";
        std::string ret; 
        std::string tmp;    
        
        if (num1.size() < num2.size()) {
            tmp = num1; 
        }
        else {
            size_t len = num2.size();
            tmp = num1.substr(0, len);
            while (true) {
                std::string dif = divide(tmp, num2);
                ret += dif;
                if (len >= num1.size()) break;
                if (tmp != "0") tmp.push_back(num1[len]);
                else tmp = std::string{num1[len]};
                len++;
            }
            if (ret.size() != 1 && ret[0] == '0')
                ret = ret.substr(1);
        }
        // 计算小数部分
        if (tmp == "0") return ret;         // 能整除，不计算小数
        else {
            for (int i = 0; i < precision; ++i) {
                tmp = (tmp == "0") ? "0" : tmp + "0"; 
                std::string dif = divide(tmp, num2);
                ret += dif;
            }
            // 最后一位保留方式
            switch (flag) {
                case DivFlag::round:
                {
                    if (tmp != "0") tmp += "0";
                    std::string last = divide(tmp, num2);
                    if (cmp_int(last, "5") == -1) break;
                    ret = add_double(ret, precision, "1", precision);
                    return ret;
                }
                case DivFlag::truncate: break;
                default: NUMBER_THROW_SWITCH_DEFAULT_OUTDATED;
            }
        }
        return to_double(ret, precision);
    }


    /**
     * @brief 浮点数除法
     * @param num1 第一个浮点数的数据部分 (即直接删除小数点)
     * @param p1   第一个浮点数的小数点位数
     * @param num2 第二个浮点数的数据部分 (即直接删除小数点)
     * @param p2   第二个浮点数的小数点位数
     * @param n    保留 n 位小数
     * @param flag true: 四舍五入  false: 截断
     * @return 返回正常的小数 (包含小数点)
     */
    std::string div_double(std::string num1, int p1, std::string num2, int p2, int precision = PRECISION, DivFlag flag = DivFlag::round) const
    {
        int p = std::max(p1, p2);
        int dif = abs(p1 - p2);
        if (dif != 0) {
            if (p1 > p2) num2 = (num2 == "0") ? num2 : num2 + std::string(dif, '0');
            else num1 = (num1 == "0") ? num1 : num1 + std::string(dif, '0');
        }
        return div_int(num1, num2, precision, flag);
    }

    std::string mod(std::string num1, int p1, std::string num2, int p2) const
    {
        std::string dif = div_double(num1, p1, num2, p2, 0, DivFlag::truncate);     // 整除
        std::string mul = mul_double(num2, p2, dif, 0);
        cal_digit_point(mul, p2);
        return sub_double(num1, p1, mul, p2);
    }
    
private:
    std::string _digit;     // 删除小数点后的数字 (数字部分)
    int         _point;     // 小数位数，则小数点位于 _digit[len - _point]
    bool        _signed;    // true: negative
    int         _width;     // 保存从流中读取数字时 (>>) 所读取的字符个数 
};

// !!! 存在 bug: 输入为 "+."，那么 '+' 无法被 putback
inline std::istream& operator>>(std::istream& is, Number& number)
{
    std::string num;
    char c = is.peek();
    bool is_float = false;
    if (c == '-' || c == '+') {
        num.push_back(is.get());
        c = is.peek();
    }
    if (c == '.') {
        is_float = true;
        num.push_back(is.get());
    }
    if (!isdigit(is.peek())) {
        if (c == '-' || c == '+' || c == '.') is.putback(c);
        if (is.good()) is.setstate(std::ios_base::failbit);
        number = Number{ "0" };
        return is;
    }
    while (true) {
        char c = is.peek();
        if (is.eof()) break;
        if (c == '.') {
            if (is_float) break;
            is_float = true;
            num.push_back(is.get());
        }
        else if (isdigit(c)) num.push_back(is.get());
        else break;
    }
    number._width = num.size();
    number._digit = std::move(num);
    number.cal_digit_point_signed(number._digit, number._point, number._signed);
    return is;
}

inline std::ostream& operator<<(std::ostream& os, const Number& number)
{
    os << number.str();
    return os;
}

}   // namespace header
